import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 617. 合并二叉树
 */
public class Solution_617 {
    /**
     * 方法二：递归（深度优先搜索）
     * <p>
     * 时间复杂度：O(min(m,n))，其中 m 和 n 分别是两个二叉树的节点个数
     * <p>
     * 空间复杂度：O(min(m,n))，其中 m 和 n 分别是两个二叉树的节点个数
     */
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }
        TreeNode merged = new TreeNode(root1.val + root2.val);
        merged.left = mergeTrees(root1.left, root2.left);
        merged.right = mergeTrees(root1.right, root2.right);
        return merged;
    }

    /**
     * 方法一：迭代（广度优先搜索）
     * <p>
     * 时间复杂度：O(min(m,n))，其中 m 和 n 分别是两个二叉树的节点个数
     * <p>
     * 空间复杂度：O(min(m,n))，其中 m 和 n 分别是两个二叉树的节点个数
     */
    public TreeNode mergeTrees1(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }
        TreeNode merged = new TreeNode(root1.val + root2.val);
        Queue<TreeNode> queue = new LinkedList<>();
        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        queue.offer(merged);
        queue1.offer(root1);
        queue2.offer(root2);
        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            TreeNode node = queue.poll(), node1 = queue1.poll(), node2 = queue2.poll();
            TreeNode left1 = node1.left, right1 = node1.right;
            TreeNode left2 = node2.left, right2 = node2.right;
            if (left1 != null || left2 != null) {
                if (left1 != null && left2 != null) {
                    TreeNode left = new TreeNode(left1.val + left2.val);
                    node.left = left;
                    queue.offer(left);
                    queue1.offer(left1);
                    queue2.offer(left2);
                } else if (left1 != null) {
                    node.left = left1;
                } else {
                    node.left = left2;
                }
            }
            if (right1 != null || right2 != null) {
                if (right1 != null && right2 != null) {
                    TreeNode right = new TreeNode(right1.val + right2.val);
                    node.right = right;
                    queue.offer(right);
                    queue1.offer(right1);
                    queue2.offer(right2);
                } else if (right1 != null) {
                    node.right = right1;
                } else {
                    node.right = right2;
                }
            }
        }
        return merged;
    }

    public static void main(String[] args) {
        Solution_617 solution = new Solution_617();
        // Tree 1
        TreeNode root1 = new TreeNode(1);
        TreeNode left1 = new TreeNode(3, new TreeNode(5), null);
        TreeNode right1 = new TreeNode(2);
        root1.left = left1;
        root1.right = right1;
        // Tree 2
        TreeNode root2 = new TreeNode(2);
        TreeNode left2 = new TreeNode(1, null, new TreeNode(4));
        TreeNode right2 = new TreeNode(3, null, new TreeNode(7));
        root2.left = left2;
        root2.right = right2;

        System.out.print("Tree 1: ");
        levelOrderPrint(root1);
        System.out.print("Tree 2: ");
        levelOrderPrint(root2);
        // 合并后
        TreeNode ans = solution.mergeTrees(root1, root2);
        System.out.print("合并后: ");
        levelOrderPrint(ans);
    }

    /**
     * 层序打印二叉树，节点为 null 则打印 null
     */
    public static void levelOrderPrint(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) {
            System.out.println(ans);
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node != null) {
                    list.add(node.val);
                    queue.offer(node.left);
                    queue.offer(node.right);
                } else {
                    list.add(null);
                }
            }
            ans.add(list);
        }
        ans.remove(ans.size() - 1);
        System.out.println(ans);
    }
}
